import java.util.PriorityQueue;

//class KthLargest {
//
//    private int k;
//    private PriorityQueue<Integer> minHeap;
//
//    public KthLargest(int k, int[] nums) {
//        this.k = k;
//        this.minHeap = new PriorityQueue<>(k);
//        // 初始化堆
//        for (int x : nums) {
//            if (minHeap.size() < k) {
//                minHeap.offer(x);
//            } else {
//                // 与堆顶元素进行比较
//                if (minHeap.peek() < x) {
//                    minHeap.poll();
//                    minHeap.offer(x);
//                }
//            }
//        }
//    }
//
//    public int add(int val) {
//        // 只需要让新元素与堆顶元素进行比较即可
//        // 需要判断堆是否满了
//        if (minHeap.isEmpty() || minHeap.size() < k) {
//            minHeap.offer(val);
//        } else if (minHeap.peek() < val) {
//            minHeap.poll();
//            minHeap.offer(val);
//        }
//        return minHeap.peek();
//    }
//}


class KthLargest {

    private int k;
    private PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        // 初始化堆
        for (int x : nums) {
            minHeap.offer(x);
            // 判断是否超出k个
            if (minHeap.size() > k) {
                // 堆顶元素一定不是第k大的
                minHeap.poll();
            }
        }
    }

    public int add(int val) {
        // 同样直接入堆
        minHeap.offer(val);
        // 再判断是否超出k个
        if (minHeap.size() > k) {
            minHeap.poll(); // 堆顶一定不是第k大的
        }
        return minHeap.peek();
    }
}